/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/candy
   @Language: C++
   @Datetime: 16-02-09 08:54
   */

// Method 1, Forward adjust, Time 34ms
class Solution {
public:
	/**
	 * @param ratings Children's ratings
	 * @return the minimum candies you must give
	 */
	int candy(vector<int> &A){
		vector<int> cd(A.size(),1);
		for(int i=1; i<A.size(); ++i){
			if (A[i]>A[i-1]) cd[i]=cd[i-1]+1;
			else if (A[i]<=A[i-1]){
				for(int j=i; j--;){
					if (A[j]<=A[j+1] || cd[j]>cd[j+1]) break;
					else ++cd[j];	// children only know neighbors
				}		
			}		
		}
		return accumulate(cd.begin(),cd.end(),0);
	}
};

// Method 2, traversal two times, Time 39ms
class Solution {
public:
	/**
	 * @param ratings Children's ratings
	 * @return the minimum candies you must give
	 */
	int candy(vector<int>& A) {
		vector<int> cd(A.size(),1);
		for(int i=1; i<A.size(); ++i)
			if (A[i]>A[i-1]) cd[i]=cd[i-1]+1;
		for(int i=A.size()-2; i>-1; --i)
			if (A[i]>A[i+1] && cd[i]<=cd[i+1])
				cd[i]=cd[i+1]+1;
		return accumulate(cd.begin(),cd.end(),0);
	}
};
